1. Field of the Invention
The invention relates to a method for navigating an object in accordance with the preamble of Patent claim 1. In said method, the object is navigated starting from a starting point to a destination along traffic routes which are contained in an electronically stored traffic route map.
2. Description of the Prior Art
Routing or navigation systems are used, for example, to direct a driver with his motor vehicle to his destination in the best way possible. Different navigation systems differ in this respect. Those of the first generation are autonomous. They merely have digitized traffic routes or road maps on CD-ROM and do not have a connection to traffic information services or service providers. For this reason, their route calculations cannot be optimized with respect to the current traffic conditions. Other disadvantageous factors are the relative speed with which the street maps become out of date and the necessity of having to obtain the appropriate data carriers whenever one wishes to drive to new, more remote regions.
In navigation systems with so-called xe2x80x9coff-boardxe2x80x9d routing, the calculation of the route is exported to a service provider. Thus, for example, a driver has the route dynamically transmitted to him after he has input his destination. The exporting of the calculation of the route and of the data material required for it has a number of advantages. Thanks to the service provider""s access to information from an extremely wide variety of sources which he can coordinate and interconnect centrally, the service provider is able to include immediately in the calculation of the routes current traffic reports, congestion forecasts, information on road works and the weather etc. In addition, the service provider can keep his data stock (digitized road maps, information on hotels, sights, public buildings etc.) more up to date and has access to relatively large quantities of data and more computing power than terminals (as cheap as possible). In this way, the driver can be guided on a route which is dynamically optimized to the respective current peripheral conditions. In addition, the procurement of new updated CD-ROMs is dispensed with. The traffic processes are thus optimized and traffic flow is made more efficient, reliable and less damaging to the environment.
It has proven a disadvantage with the two methods described above that, in order to calculate the route from the starting point to the destination, a relatively large amount of data management has to take place, and thus a large computing capacity and computing time are required.
3. Objects of the Invention
The invention is based on the object of specifying a method for navigating an object, which can be used to calculate routes more quickly using less computing power.
The way of achieving the object set is specified in the characterizing part of Patent claim 1. Advantageous refinements of the inventions can be found in the subclaims.
A method according to the invention is distinguished by the fact that the traffic routes contained in the electronically stored traffic route map are provided with routing points. These routing points contain not only information, for example in the form of a vector, on their actual geographic position (length, width) but also information on the course (for example course of the roads) lying in their vicinity, and the directions along which it is possible to navigate or drive. The routing points thus greatly facilitate the navigation and reduce the computational work which it requires.
According to a very advantageous development of the invention, the routing points are assigned routing values which, starting from the destination, either only increase or only decrease as the distance from said destination grows larger, the object being navigated using the routing values which only decrease or only increase.
The routes are calculated according to the inventive method starting from the destination in the manner, as it were, of a propagating wave with routing values.
In the process, the destination is assigned, for example, the routing value 1, while all the routing points which, viewed in the direction in which the route runs, are directly adjacent are assigned the routing value 2. The last-mentioned routing points which are directly adjacent in the direction in which the route runs are then assigned the routing value 3, and the destination is now eliminated out etc. The routing values can thus be used to guide the object starting from any position in the traffic route map. To do this, the closest routing point with the lowest routing value is used as the direction indicator because this point lies closest to the destination. The method could in principle also be implemented in such a way that it is started with a relatively high routing value at the destination, which then decreases to lower values. In this case, the navigation would take place from the starting point to the destination in the direction of increasing routing values.
The provision of the routing points with the routing values which either only increase or only decrease can be implemented relatively easily and quickly with the result that the route can be calculated in a short time and with only a small amount of computing power. The data record which is necessary for the navigation itself after the route has been created is, furthermore, relatively small, with the result that its management also requires only a small amount of computing capacity and storage capacity.
The method according to the invention can therefore also be implemented advantageously in first-generation navigation systems, provided that the traffic route maps stored on the CD-ROMs are provided with routing points. The routes can be calculated relatively quickly and with little computing power, with the result that relatively cheap terminals can be used. This applies also with respect to the fact that the data record calculated for navigation is relatively small, with the result that it also requires only a small amount of storage capacity.
However, owing to this relatively small data record which represents the calculated route, it is also possible to apply the method according to the invention advantageously even if the xe2x80x9coff-boardxe2x80x9d routing which has already been described at the beginning, in which the route is calculated by the service provider, is carried out. In this case, the calculated route must be transmitted from the service provider to the navigation system of the object which is to be navigated, which can now be carried out relatively easily, for example over a telephone link, owing to the small amount of data for the calculated route.
Apart from digital voice transmission, mobile radio also provides various possible types of data transmission, and it is now available with virtual complete coverage. Thus, the data which relate to the navigation, in this case the route calculated by the service provider, can be transmitted to the customer using an existing telephone by means of, for example, the GSM short message service SMS. Because the amount of data to be transmitted is relatively small, calling the calculated route from the service provider to the customer does not constitute a considerable cost factor, especially since the transmission of data does not require a continuous data link. The use of the method according to the invention could thus be attractive even if parts of its execution take place at the service provider end.
The method according to the invention can in principle be implemented to navigate any desired objects along traffic routes. As already mentioned, the objects can be motor vehicles which are capable of detecting their actual geographic position, for example using a GPS receiver which is carried along.
However, the objects of the type in question may also be mobile phones themselves if they are capable of detecting their actual geographic position, for example by surveying their position using a plurality of surrounding base stations. In this case also, the route calculated in advance between the starting point and the destination could be transmitted over the radiotelephone link from a service provider to the mobile phone and stored there, because the data record describing the route is relatively small, and thus can easily be buffered in the mobile phone. The user of the mobile phone could then carry out navigation in, for example, an optimum way using the display device of the mobile phone.
In the method according to the invention, according to one refinement of the invention the routing points are permanently assigned to the traffic routes, with the result that the provision of the routing points with routing values can be carried out in a simple way and relatively quickly, resulting in a relatively short computing time for the generation of the desired route. The routing points can be positioned here in the vicinity of the points where traffic routes intersect and in the vicinity of sharp bends or bends in the traffic routes. A plurality of routing points which are located one behind the other can be positioned distributed along relatively long junction-free sections of traffic routes.
If the routing points are allocated by a service provider, routing points may also be allocated temporarily, for example in the vicinity of diversions, owing to road works, accidents etc. which are set up for a limited period of time. The assignment of the routing values to the routing points is preferably made on the basis of route elements, which means that initially the routing points are provided with routing values only along part of the route lying between the destination and starting point, and then the next part of the route from the point lying closest to the destination to the starting point etc. In this way it is possible to ensure that, from any desired point on the traffic route map, a route element with the desired descending or rising sequence of routing values is always obtained in the direction of the destination.
According to another refinement of the invention, the routing values are assigned to the routing points taking into account the type of traffic route in the vicinity of the respective routing point. As a result, it is possible to take into account the fact that, in the case of one-way streets, it is possible to travel in one direction only etc.
The type of traffic route itself is determined in the vicinity of a respective routing point by means of a multidimensional vector which comprises not only branching and road-use possibilities in the respective directions but also contains information on the respective street name, the routing value (the navigation information) which is relevant in the direction of the destination and the actual geographic coordinates of the routing point. Such a vector ensures that the object will be routed reliably.
According to one development of the present invention, the size of the map excerpt is determined by the positions of the starting point and destination. The map excerpt comprises here not only the relatively close vicinity of the starting point and of the destination but also a respective region between the two points which is, for example, in the form of a tube and which can be implemented with a greater or lesser width. The width of this tube-like region and the size of the regions respectively surrounding the starting point and destination can be preset or selected by the user of the navigation system. However, the routing points have to be provided with the routing values only for the selected regions, and not for the entire traffic map, with the result that this is also a reason why only a relatively short time and small amount of computing power are required to generate the navigation route.
According to another development of the invention, when the object leaves the map excerpt, a new map excerpt is, for example called automatically, in which the routing values are assigned to the routing points with respect to the old destination and a new or instantaneous starting point, with the result that it is now also possible once more to navigate the object in the direction of the destination.
As an alternative to this, when the object leaves the map excerpt, a compass navigation back to the old map excerpt may also take place. When the object enters said old map excerpt, it is then possible to navigate again by reference to the routing values.